Adversarial Search

Adversarial search is used in games where one player's attempts to maximize their fitness (win) is opposed by another player.

The search tree in adversarial games such as tic-tac-toe consist of alternating levels where the moving (MAX) player tries to maximize fitness and then the opposing (MIN) player tries to minimize it. To find the best move the system first generates all possible legal moves, and applies them to the current board. In a simple game like tic-tac-toe this process is repeated for each possible move until the game is won, lost, or drawn. The fitness of a top-level move is determined by whether it eventually leads to a win.

Tic-tac-toe is an uninteresting game because it is possible to generate the complete game search tree. In interesting games like chess and checkers this has not been possible, due to the size of the tree. Instead programs use sophisticated evaluation functions to rate non-terminal (non won/lost/drawn) game boards.

A simple checkers evaluation function sums up values for:

Programs also use sophisticated algorithms to prune the search tree, only expanding interesting lines of play.

Here is my simple Java checkers program.

Tic-tac-toe search image based on [Russell and Norvig, 1995]

back index forward